bool isPlaceable(int queensRow[], int queensColumn[], int queenPlaced, int queenTotal, int checkerRow, int checkerColumn){
    for(int i = 0; i < queenPlaced; ++i){
        int row = queensRow[i], column = queensColumn[i];
        if(row == checkerRow) return false;
        if(column == checkerColumn) return false;
        if(column + row == checkerColumn + checkerRow) return false;
        if(checkerRow - row == checkerColumn - column) return false;
    }
    return true;
}

void move(int &checkerRow, int &checkerColumn, int queenTotal){
    ++checkerColumn;
    if(checkerColumn == queenTotal){
        checkerColumn = 0;
        ++checkerRow;
    }
}

void back(int queensRow[], int queensColumn[], int &queenPlaced, int queenTotal, int &checkerRow, int &checkerColumn){
    checkerRow = queensRow[--queenPlaced];
    checkerColumn = queensColumn[queenPlaced];
    move(checkerRow, checkerColumn, queenTotal);
}

int nQueen2(int queenTotal){
    int result = 0;
    if(queenTotal < 1){
        return result;
    }
    int *queensRow = new int[queenTotal];
    int *queensColumn = new int[queenTotal];
    int checkerRow = 0, checkerColumn = 0, queenPlaced = 0;
    while(queenPlaced > 0 || checkerRow == 0){
        if(queenPlaced != checkerRow){
            back(queensRow, queensColumn, queenPlaced, queenTotal, checkerRow, checkerColumn);
        }else if(isPlaceable(queensRow, queensColumn, queenPlaced, queenTotal, checkerRow, checkerColumn)){
            queensRow[queenPlaced] = checkerRow;
            queensColumn[queenPlaced] = checkerColumn;
            ++queenPlaced;
            if(queenPlaced == queenTotal){
                ++result;
                back(queensRow, queensColumn, queenPlaced, queenTotal, checkerRow, checkerColumn);
            }else{
                checkerColumn = 0;
                ++checkerRow;
            }
        }else{
            move(checkerRow, checkerColumn, queenTotal);
        }
    }
    delete []queensRow;
    delete []queensColumn;
    return result;
}
